package com.c2b.algorithm.leetcode.base;

/**
 * 验证回文字符串 Ⅱ
 * <p>给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。</p>
 *
 * @author c2b
 * @since 2022/5/25 16:53
 */
public class LC0680validPalindrome {

    /**
     * 最多删除一个字符，判断是否能成为回文字符串
     *
     * @param s 字符串，由小写英文字母组成，1 <= s.length <= 10^5
     * @return boolean true能，false不能
     * @author c2b
     * @since 2022/5/25 16:54
     */
    public boolean validPalindrome(String s) {
        // 如果只有一个字符,可以。如果有两个字符删除一个，还是可以
        if (s.length() <= 2) {
            return true;
        }
        // 如果是多个字符n>=3
        int left = 0;
        int right = s.length() - 1;
        char[] chars = s.toCharArray();
        while (left < right) {
            if (chars[left] != chars[right]) {
                // 如果是相邻字符,那么删除任意一个一定回文
                // 如果不是相邻字符。判断删除左边的是否回文，回文直接返回，不回文，在判断删除右边的是否回文
                return right - left == 1 || validPalindrome(chars, left + 1, right) || validPalindrome(chars, left, right - 1);
            }
            ++left;
            --right;
        }
        return true;
    }

    /**
     * 判断字符数组在指定范围中是不是回文串
     *
     * @param chars 字符数组
     * @param left  下标left
     * @param right 下标right
     * @return boolean
     * @author c2b
     * @since 2022/5/25 17:29
     */
    private boolean validPalindrome(char[] chars, int left, int right) {
        while (left < right) {
            if (chars[left] != chars[right]) {
                return false;
            }
            ++left;
            --right;
        }
        return true;
    }
}
